#include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <algorithm>

using namespace std;

class Solution {
private:
    // 单词字典
    unordered_set<string> dict;
    // 当前层和下一层的单词集合
    unordered_set<string> curLevel;
    unordered_set<string> nextLevel;
    // 反向图：key是单词，value是可以转换到key的单词列表
    unordered_map<string, vector<string>> graph;
    // 记录当前路径
    vector<string> path;
    // 最终结果
    vector<vector<string>> ans;

    // 初始化数据结构
    void build(const vector<string>& wordList) {
        dict.clear();
        for (const string& word : wordList) {
            dict.insert(word);
        }
        graph.clear();
        ans.clear();
        curLevel.clear();
        nextLevel.clear();
        path.clear();
    }

    // BFS构建反向图，返回是否能到达endWord
    bool bfs(const string& beginWord, const string& endWord) {
        bool found = false;
        curLevel.insert(beginWord);
        
        while (!curLevel.empty()) {
            // 从字典中移除当前层的所有单词，避免重复访问
            for (const string& word : curLevel) {
                dict.erase(word);
            }
            
            // 遍历当前层的每个单词，寻找下一层的单词
            for (const string& word : curLevel) {
                string w = word;
                for (int i = 0; i < w.size(); ++i) {
                    char old = w[i];
                    // 尝试替换每个位置为a-z的字母
                    for (char ch = 'a'; ch <= 'z'; ++ch) {
                        if (ch == old) continue; // 跳过相同的字母
                        
                        w[i] = ch;
                        string str = w;
                        
                        // 如果新单词在字典中存在
                        if (dict.count(str)) {
                            if (str == endWord) {
                                found = true;
                            }
                            // 构建反向边
                            graph[str].push_back(word);
                            nextLevel.insert(str);
                        }
                    }
                    w[i] = old; // 恢复原字母
                }
            }
            
            if (found) {
                return true;
            } else {
                // 交换当前层和下一层
                swap(curLevel, nextLevel);
                nextLevel.clear();
            }
        }
        return false;
    }

    // DFS回溯寻找所有路径
    void dfs(const string& word, const string& aim) {
        path.push_back(word);
        
        if (word == aim) {
            // 找到一条路径，添加到结果中（注意需要反转，因为我们是从end往begin找的）
            vector<string> temp = path;
            reverse(temp.begin(), temp.end());
            ans.push_back(temp);
        } else if (graph.count(word)) {
            for (const string& next : graph[word]) {
                dfs(next, aim);
            }
        }
        
        path.pop_back(); // 回溯
    }

public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        build(wordList);
        
        // 检查终点是否在字典中
        if (dict.find(endWord) == dict.end()) {
            return ans;
        }
        
        // BFS构建反向图，如果能到达终点则进行DFS
        if (bfs(beginWord, endWord)) {
            dfs(endWord, beginWord);
        }
        
        return ans;
    }
};
